import java.util.Scanner;

class DuoXiangshi {

    int xishu; // 系数
    int zhishu; // 指数
    DuoXiangshi next;  //指向下一个多项式节点的指针
}

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("第一次多项式的输入：");
        DuoXiangshi poly1 = create(scanner);
        System.out.println("第二次多项式的输入：");
        DuoXiangshi poly2 = create(scanner);
        DuoXiangshi sumPoly = merge(poly1, poly2);
        printt(sumPoly);
    }

    public static DuoXiangshi create(Scanner scanner) {
        DuoXiangshi head = new DuoXiangshi();  //多项式的头节点
        DuoXiangshi last = head;        //当前最后一个节点
        int coef, pow;
        do {
            DuoXiangshi p = new DuoXiangshi();
            System.out.print("请输入多项式的指数(>=0),指数为-1时退出：");
            pow = scanner.nextInt();
            if (pow == -1) {
                break;
            }
            System.out.print("请输入多项式的系数：");
            coef = scanner.nextInt();
            System.out.printf("输入成功！此次输入的多项式为： %dX^%d ", coef, pow);
            p.xishu = coef;
            p.zhishu = pow;
            last.next = p;  //将当前多项式项连接到链表中，作为上一个节点的下一个节点。
            last = p;      //更新last变量，将其指向当前多项式项。
        } while (pow != -1);
        return head;   //返回头节点head，表示创建的多项式。
    }

    public static void printt(DuoXiangshi head) {
        DuoXiangshi p = head.next;  //创建一个指向头节点下一个节点的指针p，用于遍历多项式链表
        boolean isStart = true;
        while (p != null) {
            if (p.xishu > 0 && isStart) {
                System.out.print(p.xishu + "X^" + p.zhishu);
                isStart = false;
            } else if (p.xishu > 0) {
                System.out.print("+" + p.xishu + "X^" + p.zhishu);
            } else {
                System.out.print(p.xishu + "X^" + p.zhishu);
            }
            p = p.next;   //将指针p指向下一个节点，继续遍历多项式链表
        }
        System.out.println();
    }

    public static DuoXiangshi merge(DuoXiangshi poly1, DuoXiangshi poly2) {
        DuoXiangshi head = new DuoXiangshi();
        DuoXiangshi p1 = poly1.next;  //创建一个指向第一个多项式链表的第一个节点的指针p1
        DuoXiangshi p2 = poly2.next;
        DuoXiangshi p3 = head;
        while (p1 != null && p2 != null) {
            if (p1.zhishu == p2.zhishu) {
                if (p1.xishu + p2.xishu != 0) {
                    DuoXiangshi p = new DuoXiangshi();
                    p.xishu = p1.xishu + p2.xishu;
                    p.zhishu = p1.zhishu;
                    p3.next = p;  //将新多项式项连接到合并后的多项式链表中，作为上一个节点的下一个节点
                    p3 = p;    //：更新指针p3，将其指向新多项式项
                }
                p1 = p1.next;  //将指针p1指向第一个多项式链表的下一个节点
                p2 = p2.next;
            } else if (p1.zhishu > p2.zhishu) {
                DuoXiangshi p = new DuoXiangshi();
                p.xishu = p2.xishu;
                p.zhishu = p2.zhishu;
                p3.next = p;
                p3 = p;
                p2 = p2.next;
            } else {
                DuoXiangshi p = new DuoXiangshi();
                p.xishu = p1.xishu;
                p.zhishu = p1.zhishu;
                p3.next = p;
                p3 = p;
                p1 = p1.next;
            }
        }
        p3.next = p1 != null ? p1 : p2;  //将剩余未处理完的多项式链表连接到合并后的多项式链表中
        return head;   //返回合并后的多项式的头节点。
    }
}
